using System;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0416. 分割等和子集")]
    public class No0416_CanPartition : AbsBaseTestItem
    {
        /*
        给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
        注意:
            每个数组中的元素不会超过 100
            数组的大小不会超过 200
        */

        public override void OnTest()
        {
            Assert.TestExe(CanPartition, new int[] { 1, 5, 11, 5 }, true);
            Assert.TestExe(CanPartition, new int[] { 1, 2, 3, 5 }, false);
        }

        public bool CanPartition(int[] nums)
        {
            int n = nums.Length;
            if (n < 2)
            {
                return false;
            }
            int sum = 0, maxNum = 0;
            foreach (var item in nums)
            {
                sum += item;
                maxNum = Math.Max(maxNum, item);
            }
            if (sum % 2 != 0)
            {
                return false;
            }
            int target = sum / 2;
            if (maxNum > target)
            {
                return false;
            }
            bool[] dp = new bool[target + 1];
            dp[0] = true;
            for (int i = 0; i < n; i++)
            {
                int num = nums[i];
                for (int j = target; j >= num; j--)
                {
                    dp[j] |= dp[j - num];
                }
            }
            return dp[target];
        }
    }
}
